package try01;
import java.util.*;

/*
The idea of allocate queens on board:
  a b c d e
1 X - - - -
2 - -
3 -   -
4 -     -
5 -       -

mark 1a
	mark 1b-1e, 2a-5a, right down direction to true
	allocate (n-1) from remaining locations
mark 1b-1e
(in the M th recursion, only do the marking for the M th row to speed up)
 */

public class NQueens {
	public void tester() {
		solveNQueens(1);
	}
    public List<String[]> solveNQueens(int n) {
        boolean [][] board = new boolean [n][n];
        String [] queen = new String [n];
        
        String a = "";
        for(int i =0 ; i < n ; i++) {
        	a = a+".";
        }
        for(int i =0 ; i < n ; i++) {
        	queen[i] = a;
        }
        
        if(n > 0) q(board, queen,n, n);
//        System.out.println("size: "+result.size());
//        System.out.println("count: "+count);
        return result;
    }
    
    List <String []> result = new LinkedList <String []> ();
    
//    public int count = 0;
    
    public void q(boolean [][] board, String [] config, int curr, int n) {
//    	System.out.println(n);
//    	count ++;
    	if(curr == 0) {
    		result.add(config);
//    		System.out.println(config[0]);
//    		System.out.println(config[1]);
//    		System.out.println(config[2]);
//    		System.out.println(config[3]);
//    		System.out.println();
    		return;
    	}
    	else {
    		for(int i = n-curr ; i == n-curr ; i ++) {
    			for(int j = 0 ; j < board.length ; j++) {
    				if(board[i][j] == false) {
    					board[i][j] = true;
    					boolean [][] board2 = deepcopy(board);
    					String [] config2 = deepcopy(config);
    					
    					markqueen(config2, i, j);
    					mark(board2, i, j);
    					
//    					System.out.println(config[0]);
//    					System.out.println(config2[0]);
    					
    					q(board2, config2, curr-1, n);
    				}
    			}
    		}
    	}
    }
    
    public boolean [][] deepcopy(boolean [][] s) {
    	boolean [][] d = new boolean [s.length][s.length];
    	for(int i = 0 ; i < s.length ; i++) {
    		for(int j = 0 ; j < s.length ; j++) {
    			d[i][j] = s[i][j];
    		}
    	}
    	return d;
    }
    
    public String [] deepcopy(String [] s) {
    	String [] d = new String [s.length];
    	for(int i =0 ; i < s.length ; i++) {
    		d[i] = s[i];
    	}
    	return d;
    }
    
    public void markqueen(String [] s, int r, int c) {
//    	System.out.println(s[0]);
    	s[r] = substitute(s[r], c);
//    	System.out.println(s[0]);
    }
    
    public String substitute(String s, int a) {
    	if(a+1 < s.length())
    		return s.substring(0, a) + "Q"+s.substring(a+1);
    	return s.substring(0, a) + "Q";
    }
    
    public void mark(boolean [][] board, int r, int c) {
    	int n = board.length;
    	for(int i =0 ; i < n ; i++) {
    		board[r][i] = true;
    		board[i][c] = true;
    		
    		if(r + i < n && c + i < n)
    			board[r+i][c+i] = true;
    		if(r + i < n && c - i >= 0)
    			board[r+i][c-i] = true;
    		if(r - i >= 0 && c + i < n)
    			board[r-i][c+i] = true;
    		if(r - i >= 0 && c - i >= 0)
    			board[r-i][c+-i] = true;
    		
    	}
    }
}